/*
 * @lc app=leetcode.cn id=210 lang=typescript
 *
 * [210] 课程表 II
 */

// @lc code=start

//  思路：拓扑排序
//  拓扑排序 = 后序遍历反转之后的结果，且只用于有向无环图，需环检测
//  参考：https://labuladong.github.io/algo/2/20/35/

function findOrder(numCourses: number, prerequisites: number[][]): number[] {

    const visited: boolean[] = []
    const postorder: number[] = []
    const onPath: boolean[] = []
    let hasCycle: boolean = false

    // 创建邻接表
    const buildGraph = (numCourses: number, prerequisites: number[][]): number[][] => {
        const graph: number[][] = []
        for (let i = 0; i < numCourses; i++) {
            graph[i] = []
        }
        for (const edge of prerequisites) {
            const from = edge[1], to = edge[0]
            graph[from].push(to)
        }
        return graph
    }
    const traverse = (graph: number[][], index: number) => {
        if (onPath[index]) hasCycle = true   // 出现环
        if (visited[index] || hasCycle) return  // 找到环/访问过

        visited[index] = true
        onPath[index] = true

        for (const i of graph[index]) {
            traverse(graph, i)
        }
        // 后续遍历位置
        onPath[index] = false
        postorder.push(index)
    }
    const graph = buildGraph(numCourses, prerequisites)
    for (let i = 0; i < numCourses; i++) {
        traverse(graph, i)
    }

    if (hasCycle) return []  // 有环
    // 将后序遍历结果反转
    postorder.reverse()
    const res = new Array(numCourses).fill(0)
    for (let i = 0; i < numCourses; i++) {
        res[i] = postorder[i]
    }
    return res
};
// @lc code=end

console.log(findOrder(2, [[0, 1], [1, 0]]))
console.log(findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]))
